package nowCoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by Ghost on 2015/3/27.
 */
public class 求正数数组的最小不可组成和 {
    ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();

    private void findCombination(int[] arr, int start){

        if(start==arr.length-1){
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(arr[start]);
            if(!rst.contains(tmp))
                rst.add(tmp);
        } else{
            int[] tt = new int[arr.length-start];
            for(int i=start;i<arr.length;i++){
                tt[i-start] = arr[i];
                int t = arr[start];
                arr[start] = arr[i];
                arr[i] = t;
                findCombination(arr,start+1);
                t = arr[start];
                arr[start] = arr[i];
                arr[i] = t;
            }
            Arrays.sort(tt);
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            for(int a:tt)
                tmp.add(a);
            if(!rst.contains(tmp))
                rst.add(tmp);
        }
    }
    public int getFirstUnFormedNum(int[] arr) {
        rst.clear();
        int min = arr[0], sum=0;
        for(int a:arr){
            if(a<min){
                min = a;
            }
            sum+=a;
        }

        findCombinatins(arr);
        HashMap<Integer, Boolean> hashMap = new HashMap<Integer, Boolean>();
        for(ArrayList<Integer> l:rst){
            int s=0;
            for(int a:l){
                s+=a;
            }
            hashMap.put(s,true);
        }
        for(int i=min+1;i<sum;i++){
            if(!hashMap.containsKey(i))
                return i;
        }
        return sum+1;
    }

    private void findCombinatins(int[] arr){
        int n = arr.length;
        int Max = (int) (Math.pow(2,n));
        for(int i=1;i<Max;i++){
            int index = 0;
            int tmp = i;
            ArrayList<Integer> t = new ArrayList<Integer>();
            while(tmp!=0){
                int a = tmp & 1;
                if(a!=0)
                    t.add(arr[index]);
                tmp>>=1;
                index++;
            }
            rst.add(t);
        }
    }
    public static void main(String[] args){
        求正数数组的最小不可组成和 qiu = new 求正数数组的最小不可组成和();
        int[] arr= {3,3,1,10,6,9,8,5,7};
        System.out.println(qiu.getFirstUnFormedNum(arr));
    }
}
